Dynamic Object Language Labs Presents

Object Oriented Inference Tool

DOLL Inference Tool - A technical Description

DOLL, Inc. has an inference tool that is based on C++ class libraries, and DOLL's compiler and development environment technology. The tool includes an inference engine that supports backward and forward chaining expert system technology. The tool also includes a truth maintenance capability, and grapical rule debugging aids. The inference tool was developed as part of consulting projects with various customers and has proven to be so generally useful, that DOLL is now making a product version. The first version will be available for Sun workstations running SunOS. Later versions will support OS/2, Windows NT and Solaris.

The inference toll is the first in a series of Object Intelligent Tools from DOLL, all based on proven class library technology.

Forward Chaining in the DOLL Inference Tool

The forward chaining capability of the inference engine consists of a compiler for a rule syntax that is an extension of C++. The rules include a condition part, often called the left hand side, and an action part, called the right hand side (RHS). All objects manipulated by the rule system are C++ objects defined by the user. The rule system compiler creates C++ functions for the rules and arranges for the rules to be linked in to the RETE network that is supported by the library. A database of facts is supported that can be persistent, and serves as the basis for the rule system interaction. After the rules have been compiled by the rule compiler, the result is C++ code that can be linked with the forward chaining library and the rest of the application. The class library contains functions that support manipulation of the rule system at runtime, and the obtaining and printing of diagnostic information. The state of the rule system can be interrogated from a C++ debugger (such as the GNU debugger). The system is designed to be debugged in the context of a C++ development environment.

The basic concept for forward chaining is that when the LHS is true, and the rule is selected, do the RHS. The LHS is a list of 4-tuples to be matched, each tuple including:

object type
name
bindings
and optionally constraints

The RHS consists of a function to invoke for a rule firing, and miscellaneous documentation. When the constraints are true for some combination of objects whose classes match those specified in the LHS of a rule, and the rule is selected (see below under conflict resolution), the function part of the RHS is invoked. The method invoked can add, remove or modify working memory objects, or otherwise side effect the system.

Conflict Resolution under Forward Chaining

Evaluation is performed in cycles. In each cycle, there are zero or more rules that could fire. The set of such rules is called the conflict set. If the conflict set is empty, the rule system stops. Otherwise one rule must be selected. This is done with a conflict resolution method called fcSelectRuleToRun. This can be specialized by subclasses of the rule system, but a default one is provided that selects on the following criteria, in descending order of importance:

Sort by age of object in sequence order.
Sort by specificity of expression in rule.
Sort by number components.
Arbitrary.

Backward Chaining in the DOLL Inference Tool

The backward chaining works similar to the forward chaining capability. It uses the same database as the forward chaining system so that forward and backward subsystems can use the same data, and can be called from each other (most typically by calling a backward chaining ruleset from the RHS of a forward chaining system). The class library contains support for the manipulation of confidence factors used in quantifying uncertainty -- usually in diagnostic systems.

The concept of backward chaining is that when the RHS of a rule is sought, and the rule is selected, prove LHS. As a side effect, when all conditions of a rule's LHS are established, a WME representing the RHS is added to the working memory. The LHS consists of a list of object names to be sought, while the RHS consists of the expression to be satisfied, a method to invoke when satisfied, and miscellaneous documentation.

Evaluation is achieved by 'asking' for a fact. If the fact can be proven, it is returned. Logic variable binding is provided and used to support the backward chaining engine.

Working Memory/Cache

The working memory (or cache), is implemented as an OODB (for persistance), containing a collection of objects that inherit from WMEObject. Also, a persistant RETE net is associated with the working memory. Whenever an object is added to the working memory, it is run through the RETE net to update the forward chaining status. A working memory object is assigned a timestamp at the time that it is added to the working memory. This can be used in conflict resolution. A working memory element is given a 'assertedby' attributed when it is added to the working memory. If the object is added by a forward chaining rule, the rule and the list of working memory objects bound by that rule is the 'assertedby', similarly, if it is added by a backward chaining rule, the rule and the set of satisfied LHS objects is the 'assertedby'. If the object is added by an external mechanism, the assigned by is some subclass of AxiomaticFact. This chain describes exactly how a fact came to be asserted.

Architechture and Design of the Libraries

Most expert systems are parts of larger applications, rather than simply stand-alone applications themselves. For that reason, it is extremely advantageous to integrate rule based processing into a modern C++ application, and to achieve the incremental benefits of a rule system while maintaining a well engineered, object oriented solution, that is efficient, portable, debuggable and robust. We believe that the best way to achieve this integration is to have:

Working elements are C++ objects, that inherit from WMEObject.
The state of a rule system is encapsulated in its working memory (also known as it's cache).
Rules are extesions of C++ syntax.
Forward chaining actions are straight C++ code (for debuggability).

If most of your program is C++, you want to debug the program with a native C++ debugger. The rule system consists of a few objects that may be interrogated with a copnventional debugger, such as a conflict set, and a working memory. Most of the actual code exists in the action routines. We separate the action routines from the rule, so that when debugging the execution of the action routine, you will see the source code that you wrote rather than a generated output from preprocessor. This arrangement is very portable,a nd doesn't depend on platform specific features such as intermediate C++ source code annotation conventions. Debugging LHS state is not easy on any system since the LHS components are computed as working memory is adjusted. This is best debugged by looking at the conflict set and the working memory from within the conflict resolution procedure. By examining what is in the working memory, and what rules you expected to find ready to fire, you can debug deviations from your expectation.

With reasonably large systems (and most are, since small systems don't merit the approach), efficiency is of utmost importance. The rules MUST be compiled. C++ provides an ideal way of providing in a platform independant way, a portable compilation and debugging engine that has full support for system calls and I/O. The rule system preprocessor doesn't need to reinvent compilation, debugging, I/O, or any other form of system integration. Significant robustness is achieved through this approach, and rule systems can trivially be built into existing C++ based applications. Conventional databases can trivially be accessed via C calls, as can existing multimedia, network, and other system services.

The advantages of the DOLL system are that it is:

simple,
fully compiled to C++, and
efficient.

As the source code is (optionally) provided, it can be extended or modified to suit unforeseen needs.

Formal Syntax of Rules

The design of the syntax for rules is goverened by the following objectives:

Separation of rule syntax from C++
Terse rule encapsulation.
Representation of a rule as an object.
Suitability of rule to support forward and backward chaining paradigms.
Ease of reading and compilation.

The following is the basic syntax for the rule language:

rules:: { rule }*
rulename:: 'identifier'
variable:: 'identifier'
attribute:: 'identifier'
classname:: 'identifier'
bname:: 'identifier'
ruletype:: 'forward_rule'
'backward_rule'
rule:: rulename ruletype '{' { vap }* '}'
vap:: attribute ':' value ';'
value:: working-memory-matchlist
c-expression
working-memory-matchlist:: working-memory-match { ',' working-memory-match }*
working-memory-match:: { '~' }1 '{' classname bname bindlist constraints '}'
bindlist:: '[' { binding-expression }* ']'
binding-expression:: variable '=' c-expression
constraints:: constraint { boolean-combinator constraint }*
boolean-combinator:: 'and'
'or'
constraint:: { 'not''('c-expression')' }1

Base Classes

The rule system as compiled is represented during runtime as a collection of objects stored in an OODB.

class RuleSystem;

This class may be subclassed by the application in order to specialize and extend certain core functionality. Most commonly, the conflict resolution algorithm can be modified in this way. There is only a single instance of diRuleSystem in most applications, although a segmented problem could make arbitrarily many of them, all as different classes, and use them like intelligent agent subroutines.

class WMEObject;

All Working memory objects are instances of subclasses of WMEObject. WMEObject provides basic support for being a working memory object, especially:

Rete processing.
Timestamping.
Reference counting.

class SET;

A persistant set object for representing all sets in the rule system. In particular, it is used for the conflict set.

class ReferenceCounted;

A superclass of WMEObject that provides simple reference counting. It is used by the working memory to provide for automatic deletion of objects that no one else knows about. Objects that must continue to exist, must have their reference count ticked before adding them to the working memory.

class Confidence;

A class used to represent uncertainty. A simple implementation of uncertainty is provided by default (similar to cf used in E-Mycin). Systems where managing uncertainty is of greater import can subclass Confidence and implement more rubust schemes -- such as Dempster Schaeffer based schemes.

A short 5 rule example

Would you like to see a small example?

Back